home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Archives / Replacements / simplesort.lha / simplesort.doc < prev    next >
Encoding:
Text File  |  1994-10-06  |  9.1 KB  |  253 lines
  1. =====================================================================
  2.                            SimpleSort V1.0
  3. =====================================================================
  4.  
  5.                      (C) 1993/94 Helmut Neumann
  6.  
  7.                 *DAS*  Sortierprogramm für den Amiga
  8.  
  9.  
  10.  
  11.  
  12. 0. Nutzungsbedingungen
  13. ======================
  14.  
  15.  
  16. Dieses  Programm  wird  unter  der Idee der Share-Ware angeboten, die
  17. Nutzung  ist  zu  Test-Zwecken frei.  Bei Gefallen und weitergehender
  18. Nutzung  ist eine Gebühr von 10,- DM an mich zu entrichten.  Ich kann
  19. natürlich  eine  Nutzung  des Programm nicht kontrollieren, aber über
  20. Bugreports  nicht  registrierter Benutzer bin ich verständlicherweise
  21. nicht  sehr  erfreut.   Es  wird  keine  eingeschränkte  Version  des
  22. Programms zu Testzwecken geben, ich kann also nur an das Gewissen der
  23. Viel-Nutzer  appellieren  sich registrieren zu lassen.  Ich übernehme
  24. keinerlei  Garantie  für Fehlerfreiheit des Programms.  Die Anwendung
  25. dieses  Programms  kann  die  üblichen  Fehler bis hin zu Verlust der
  26. Daten der Platte bei unglücklichen Abstürzen hervorrufen.  Das Archiv
  27. darf    ausschließlich   mit   der   unveränderten   Anleitung,   der
  28. BUGREPORT.FORM,  SimpleSort  und  SimpleSort020  weitergegen  werden.
  29. Weitere  Dateien  haben  im Archiv nichts zu suchen.  Die Verursacher
  30. von   .displaymes  und  anderen  schwachsinnigen  Texten  werden  mit
  31. Lindenstraße nicht unter 10 Folgen bestraft (mit Ton !!).
  32.  
  33.  
  34.  
  35.  
  36. 1. Einführung
  37. =============
  38.  
  39.  
  40. 1.1. Das War :-( (Motivation)
  41. -----------------------------
  42.  
  43. Jeder  der  bislang den Dos-Befehl Sort benutzen mußte wird zweierlei
  44. festgestellt   haben   :    Er   braucht  mindestens  die  Länge  der
  45. Eingabedatei  und  er  ist vor allem recht langsam.  Zwischenzeitlich
  46. kamen  mehrere Alternativen heraus, von denen llsort zwar schnell ist
  47. aber   die   doppelte   (!)  Länge  der  zu  sortierenden  Datei  als
  48. zusammenhängenden  Speicherblock  braucht.   Weiterhin  gibt  es noch
  49. avlsort,  welches sich neben seines Mindestspeicherbedarfs (auch hier
  50. Länge  der  Eingabedatei) ebenso wie der Dos-Sort-Befehl durch extrem
  51. langsame  IO-Routinen auszeichnet.  Dies ist alles nicht befriedigend
  52. und  spätestens  bei  allen  Dateien  die  größer  als der verfügbare
  53. Hauptspeicher sind wird die Sortierung entweder unmöglich oder extrem
  54. (!)    langsam    (wenn   man   den   Umweg   über   eine   virtuelle
  55. Speicherverwaltung geht).
  56.  
  57.  
  58. 1.2. Das Ist :-)
  59. ----------------
  60.  
  61. Nun  ist  die  erste  Version  des  Sortierers  fertig, der all diese
  62. Nachteile ausbügelt.  Hier die wichtigsten Features im Überblick :
  63.  
  64. - Die Größe der sortierbaren Dateien ist lediglich durch den 
  65.   Plattenplatz beschränkt. 
  66.  
  67. - Der vom Sortierer zu benutzende Speicher kann genau vorgegeben
  68.   werden.
  69.  
  70. - Es werden ausgereifte Caching-Routinen eingesetzt, um die üblichen
  71.   Nachteile bei Zeilenweisem Einlesen und Wegschreiben zu beheben.
  72.  
  73. - Um ein vielfaches schneller als die bislang verfügbaren
  74.   Sortierprogramme auf dem Amiga.
  75.  
  76. - Das append odd-length problem wird zur Steigerung der
  77.   IO-Geschwindigkeit erkannt und behoben.
  78.  
  79.  
  80.  
  81.  
  82. 2. Anwendung
  83. ============
  84.  
  85.  
  86.  
  87. 2.1 Programmaufruf
  88. ------------------
  89.  
  90. SimpleSort   sortiert   eine   vorgegebene  (ASCII-)  Datei  auf  die
  91. Zieldatei.   Die  Syntax  ist  in  der  Minimal-Angabe  Analog zu den
  92. bisherigen  Sortierprogrammen und erfordert mindestens die Angabe des
  93. Namens der Eingabedatei und der Ausgabedatei : 
  94.  
  95. SimpleSort infile outfile
  96.  
  97.  
  98.  
  99. 2.2 Optionen
  100. ------------
  101.  
  102. Zusätzlich  sind  zur  Steuerung  des Default-Verhaltens des Programm
  103. noch  weitere  Optionen  vorgesehen,  welche  hinter  dem  Namen  der
  104. Eingabe- und der Ausgabe-Datei angegeben werden können :
  105.  
  106.  
  107. -quiet
  108.  
  109. Es    werden    sämtliche   Ausgaben   des   Programms   incl.    der
  110. Copyright-Meldung     unterdrückt.     Ausgenommen    hiervon    sind
  111. Fehlermeldungen.
  112.  
  113.  
  114. -maxmem
  115.  
  116. SimpleSort  darf  den  ganzen Speicher abzüglich einer Reserve von 10
  117. Prozent des momentanen Fastmems benutzen.
  118.  
  119.  
  120. -sloppy
  121.  
  122. Diese  Option  ermöglicht  die  Sortierung  von  Binär-Dateien.   Die
  123. Ausgabedatei kann hierbei eine geringfügig andere Länge haben.
  124.  
  125.  
  126. -outbufsize size
  127.  
  128. Mit  dieser  Option  kann man die Größe des Output-Buffers bestimmen.
  129. size  wird  als  gewünschte Bytes aufgefaßt, ein Wert von weniger als
  130. 10000  Bytes  ist  nicht sinnvoll und wird (ohne Fehlermeldung) nicht
  131. akzeptiert.  Default-Wert ist 256000 Bytes.
  132.  
  133.  
  134. -inbufsize size
  135.  
  136. Mit  dieser  Option  kann  die  Größe  des  Eingabepuffers festgelegt
  137. werden.   10  Prozent dieses Speichers gehen allerdings für das Array
  138. mit  den  Zeilennummern drauf.  Als Default-Wert wird hier die Hälfte
  139. des  momentan  verfügbaren  Fastmems genommen, oder wenn kein Fastmem
  140. verfuegbar ist (z.B.  roher A1200) entsprechend das Chipmem.  Es wird
  141. aber  immer  die  Reserve  berücksichtigt,  das  heißt  wenn man mehr
  142. Speicher  angibt als tatsächlich abzüglich der Reserve verfügbar ist,
  143. dann ist das auch kein Problem.
  144.  
  145.  
  146. -reserve size
  147.  
  148. Diese   Option   bietet  in  Kombination  mit  -maxmem  eine  bequeme
  149. Möglichkeit  eine  Arbeitskonfiguration  über  den  vom  Programm  zu
  150. belassenen  freien  Speicher  zu definieren.  Hierbei ist als Reserve
  151. ausschließlich  Fastmem  gemeint,  hinzu  kommt  noch  eventuell  ;-)
  152. vorhandenes  Chipmem,  welches  nach  Möglichkeit  gar nicht tangiert
  153. wird.
  154.  
  155.  
  156.  
  157.  
  158. 3. Interna 
  159. ===========
  160.  
  161.  
  162.  
  163. 3.1. (wie machen die das bloß :)
  164. --------------------------------
  165.  
  166. SimpleSort  verhält  sich  bei  Dateien die bequem ins Fastmem passen
  167. genau  so  wie  die  bisherigen  Sortierprogramme,  es ist nur um ein
  168. vielfaches  schneller.  Hierbei ist zu beachten, daß SimpleSort nicht
  169. (!)  automatisch  den  maximal  möglichen Speicher reserviert sondern
  170. immer  die  Hälfte.   Wer mehr wünscht, und das kann manchmal bei der
  171. Sortierung  von  Dateien  in  einem Rutsch sinnvoll sein, der muß die
  172. Option  -maxmem verwenden oder die Größe des zu benutzenden Speichers
  173. mit -inbufsize einstellen.
  174.  
  175. Wenn  nun  aber  Dateien sortiert werden müssen, welche leider länger
  176. sind   als   der   verfügbare  Speicher  teilt  simplesort  diese  in
  177. vorsortierte Teildateien auf.  In einem zweiten Schritt (nach Meldung
  178. Phase   1   beendet)   werden   dann  diese  Einzeldateien  nach  dem
  179. Merge-Sort-Prinzip  (sortieren  von  mehreren  bereits  vorsortierten
  180. Einzeldateien  (Bändern))  zu  einer neuen sortierten Datei.  Hierbei
  181. machen  sich  besonders  die Cache-Routinen besonders bemerkbar, ohne
  182. die  das  ganze  doch  ETWAS  langsamer  wäre, die HD-Lampe würde nur
  183. glimmen, die HD würde kräftig rappeln und die Gesamt-Performance wäre
  184. lausig.   Die größte in der Testphase sortierte Datei war ein Logfile
  185. mit  66  MB  Länge.  Diese Datei wurde mit einer Hauptspeichernutzung
  186. von lediglich 1.5 MB in ca.  15 Minuten klaglos sortiert !
  187.  
  188. Der  Nachteil des ganzen, wenn man überhaupt davon sprechen kann, ist
  189. daß man kurzfristig die zweifache Länge der zu sortierenden Datei auf
  190. der   Zielplatte   benötigt.    Es  wäre  noch  möglich  eine  Option
  191. einzubauen,  die  nach  Abschluß  der  ersten  Phase die Eingabedatei
  192. löscht, ich weiß aber nicht wie praxisgerecht dies wäre.
  193.  
  194.  
  195.  
  196. 3.2. Was machen die bloß nicht :-(
  197. ----------------------------------
  198.  
  199. Tja,   leider   hat   die  Geschwindigkeit  auch  hier  ihren  Preis.
  200. SimpleSort  ist kein vollständiger Ersatz des Dos-Sort.  Es kennt zum
  201. Beispiel  die  Option  Colstart nicht.  Weiterhin sortiert SimpleSort
  202. schlicht  nach  den ASCII-Werten, was manchmal zu anderen Ergebnissen
  203. als  die  der  bisherigen Sortierer führt.  SimpleSort ist auch nicht
  204. Pipe-fähig,  es lassen sich damit in der momentanen Version lediglich
  205. Dateien sortieren.
  206.  
  207.  
  208.  
  209. 3.3. Known bugs :-((
  210. --------------------
  211.  
  212. Es  gibt  einen  Fehler  im  Quicksort  (es  wird  der  vom  Compiler
  213. angebotene   benutzt)  der  dazu  führt  daß  dieser  bei  bestimmten
  214. Eingabekonfigurationen  nicht terminiert.  Dies hängt anscheinend von
  215. der  Anzahl  der  zu sortierenden Zeilen und der Konsistenz der Daten
  216. ab.  Ich hatte bisher zwar lediglich eine Beispieldatei finden können
  217. bei  der  sich  dieses  Verhalten  zeigte  (eine 4 MB lange Liste von
  218. einzelnen  Wörtern),  aber einmal ist einmal zuviel.  Abhilfe schafft
  219. hier  nur  die  Reduzierung  des  inbufsize,  dann werden auch solche
  220. Dateien ordentlich sortiert.  Sollte sich dieser Fehler in der Praxis
  221. in  der  realen  Welt  häufiger  zeigen  werde ich wohl den Quicksort
  222. selbst programmieren. Bei Dateien die nicht mit einem cr enden werden
  223. in der Zieldatei alle Zeichen danach abgeschnitten.
  224.  
  225.  
  226.  
  227. 4. Nachwort (Shareware-Info)
  228. ============================
  229.  
  230. Die  Entwicklung  dieses  Programms  hat mich einige Arbeit gekostet.
  231. Ich  bitte  jeden  dies  bei Gefallen zu honorieren und die Gebühr zu
  232. entrichten.   Eine  Weiterentwicklung  des  ganzen  ist  auch von der
  233. Resonanz  abhängig. Meine Bankverbindung lautet :
  234.  
  235. Helmut Neumann
  236. Stadtsparkasse Aachen
  237. Blz.  39050000
  238. Konto 16012726
  239.  
  240. Bei Übersendung des Geldes bitte eine Mail an mich zur Information.
  241.  
  242. Bug-Reports   bitte   DETALLIERT  (notfalls  mit  den  verursachenden
  243. Dateien)  an  mich  senden.   Ich  bitte  auch  am  Anfang,  wo  sich
  244. wahrscheinlich  einige  DICKE  Fehler  zeigen,  um  sofortige Meldung
  245. derselben  und  um  Meldung  eigener  Bedürfnisse.   Dazu  bitte  die
  246. bugreport.form  verwenden.   Ich bin im Netz unter folgenden Adressen
  247. erreichbar :
  248.  
  249. Z-Netz   : helmutn@tron.gun.de
  250. Internet : helmutn@tron.gun.de
  251.  
  252. Bis dann, Helmut.
  253.